package com.cqs.leetcode.string;

import java.util.Stack;

/**
 * @author lixiaowen
 * @create 2020-01-01
 */
public class MinimumAddtoMakeParenthesesValid941 {

    static class Solution {
        public int minAddToMakeValid(String str) {
            Stack<String> stack = new Stack<>();
            int sum = 0;
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (c == '(') {
                    stack.push("(");
                } else {
                    if (!stack.isEmpty()) {
                        stack.pop();
                    } else {
                        ++sum;
                    }
                }
            }
            return sum + stack.size();
        }
    }

    static class Solution2 {
        public int minAddToMakeValid(String str) {
            int left = 0, right = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '(') {
                    left++;
                } else {
                    if (left > 0) {
                        --left;
                    } else {
                        ++right;
                    }
                }
            }
            return left + right;
        }
    }
}
